package first

/*
	给你一个只包含 '('和 ')'的字符串，找出最长有效（格式正确且连续）括号子串的长度。

	示例 1：
	输入：s = "(()"
	输出：2
	解释：最长有效括号子串是 "()"

	示例 2：
	输入：s = ")()())"
	输出：4
	解释：最长有效括号子串是 "()()"

	示例 3：
	输入：s = ""
	输出：0
	提示：

	0 <= s.length <= 3 * 104
	s[i] 为 '(' 或 ')'

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/longest-valid-parentheses
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func LongestValidParentheses(s string) int {
	return longestValidParentheses(s)
}

func longestValidParentheses(s string) int {
	if len(s)<=1{
		return 0
	}
	dp := make([]int, len(s)) // dp[i]表示下标为i的字符结尾的最长有效子字符串的长度(注意、需要包含s[i]本身)。
	// initialize
	dp[0] = 0
	if s[1] == '(' {
		dp[1] = 0
	} else {
		if s[0] == '(' {
			dp[1] = 2
		} else {
			dp[1] = 0
		}
	}
	longest := dp[1]
	for i := 2; i < len(s); i++ {
		if s[i] == '(' {
			dp[i] = 0
		} else { // s[i]==')'
			if s[i-1] == '(' {
				dp[i] = dp[i-2] + 2
			} else { // s[i-1]==')'
				if i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] == '(' {
					dp[i] = dp[i-1] + 2
					if i-dp[i-1]-2 >= 0 {
						dp[i] += dp[i-dp[i-1]-2]
					}
				}
			}
		}
		longest = max(longest, dp[i])
	}
	return longest
}
